---
title: "完美正方形"
created: 2025-11-28
tags:
  - 算法
---

# 完美正方形

## 题目 [完美正方形](https://www.lanqiao.cn/problems/685/learning/)

![[image-1cf4ec5f.png]]

## 思路分析

写不了一点

## 代码实现

```cpp
#include <iostream>

using namespace std;

int square[19] = {2, 5, 9, 11, 16, 17, 19, 21, 22, 24, 26, 30, 31, 33, 35, 36, 41, 50, 52};

int visited[19] = {0};

int grid[154][154] = {0};

bool solve()

{

  for(int i = 153; i >= 0; i--)

  {

    for(int j = 153; j >= 0; j--)

    {

      if(!grid[i][j])

        return 0;

    }

  }

  return 1;

}

bool judge(int hang, int lie, int square)

{

  if(hang + square > 154 || lie + square > 154)

    return 0;

  for(int i = hang; i < hang + square; i++)

  {

    for(int j = lie; j < lie + square; j++)

    {

      if(grid[i][j])

        return 0;

    }

  }

  return 1;

}

void fill(int hang, int lie, int square, int num)

{

  for(int a = hang; a < hang + square; a++)

  {

    for(int b = lie; b < lie + square; b++)

      grid[a][b] = num;

  }

}

bool DFS(int hang, int lie)

{

  if(solve())

    return 1;

  int end = 1;

  int a, b;

  for(a = hang; a < 154 && end; a++)

  {

    for(b = 0; b < 154 && end; b++)

    {

      if(!grid[a][b])

      {

        hang = a;

        lie = b;

        end = 0;

      }

    }

  }

  for(int i = 18; i >= 0; i--)

  {

    if(!visited[i] && judge(hang, lie, square[i]))

    {

      visited[i] = 1;

      fill(hang, lie, square[i], square[i]);

      if(DFS(hang, lie + square[i]))

        return 1;

      visited[i] = 0;

      fill(hang, lie, square[i], 0);

    }

  }

  return 0;

}

int main()

{

  fill(0, 0, 47, 47);

  fill(0, 47, 46, 46);

  fill(0, 93, 61, 61);

  DFS(46, 47);

  for(int i = 0; i < 154;)

  {

    cout << grid[153][i] << ' ';

    i += grid[153][i];

  }

  return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[第六届蓝桥杯大赛软件赛决赛C-C++ 大学 B 组|第六届蓝桥杯大赛软件赛决赛C/C++ 大学 B 组]] 🏠 [[00-冲刺国赛]] ➡️ [[密文搜索|密文搜索]]